/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package compiler.parser;

import compiler.grammar.NonTerminal;
import compiler.grammar.Production;
import compiler.grammar.Symbol;
import compiler.grammar.Terminal;
import compiler.parser.lalr.LALRItem;
import compiler.parser.lalr.LALRState;
import compiler.parser.lalr.LALRUtils;
import compiler.parser.lalr.LALRUtils.Action;
import compiler.parser.lalr.LALRUtils.GotoData;
import compiler.parser.lalr.LALRUtils.Reduce;
import compiler.parser.lalr.LALRUtils.ReduceData;
import compiler.parser.lalr.LALRUtils.Shift;
import compiler.parser.lalr.LALRUtils.ShiftData;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 *
 * @author meemo
 */
public class LALRParsingTableGen
{
    //~ Instance fields --------------------------------------------------------

    private Collection<LALRState> lalrStates;
    private LALRParsingTable      parsingTable;
    private Map<String, Symbol>   symbols;
    private Production            startProd;

    //~ Constructors -----------------------------------------------------------

    public LALRParsingTableGen(Map<String, Symbol> symbols, Collection<LALRState> lalrStates, Production startProd)
    {
        this.symbols      = symbols;
        this.lalrStates   = lalrStates;
        this.startProd    = startProd;
        this.parsingTable = computeParsingTable();
    }

    LALRParsingTableGen(LALREngine engine)
    {
        this(engine.getSymbols(), engine.getStates(), engine.getStartProduction());
    }

    //~ Methods ----------------------------------------------------------------

    public LALRParsingTable getParsingTable()
    {
        return parsingTable;
    }

    private LALRParsingTable computeParsingTable()
    {
        Map<Integer, Terminal>    terminals = new HashMap<Integer, Terminal>();
        Map<Integer, NonTerminal> nonTerminals = new HashMap<Integer, NonTerminal>();

        for (Symbol s : symbols.values())
        {
            if (s instanceof Terminal)
            {
                terminals.put(s.getId(), (Terminal)s);
            }
            else if (s instanceof NonTerminal)
            {
                nonTerminals.put(s.getId(), (NonTerminal)s);
            }
        }

        terminals.put(Terminal.EOF.getId(), Terminal.EOF);

        // LALRState.AllStatesByKernel
        Action[][] actionTable; // state No., terminal No. , element: Action (
                                // Shift( state no. ) or reduce( prod no. ) )

        int[][]    gotoTable; // state No., non-terminal No., element: state no

        // an accepting state will be in ActionTable a Reduce by Prod 1 ( S' = S
        // ) in the column of $
        actionTable = new Action[lalrStates.size()][terminals.size() + 1];
        gotoTable   = new int[lalrStates.size()][nonTerminals.size()];

        final int defaultAction = terminals.size();

        int       numConflictShiftReduce = 0;
        int       numConflictReduceReduce = 0;

        for (LALRState state : lalrStates)
        {
            // state.StateID

            // Solve shift/reduce, by shifting,
            // Solve reduce/reduce, by the lowest ID ( the one which cam first
            // in the specifications )
            ArrayList<ShiftData> shifts = LALRUtils.getShiftsOf(state); // returns pair list: TerminalID, and stateID if the list is empty Do reduce

            for (ShiftData sd : shifts)
            {
                actionTable[state.getId()][sd.terminalId] = new Shift(sd.stateID);
            }

            /* returns pair list: TerminalID List ( the contents of the lookahead ),
             and ProductionID if length is > 1 , ReduceReduce conflict,
             choose one the one that was already processed ( with overlapping lookaheads )
             if shifts > 0, and reduce > 0 then ShiftReduce conflict, and do the Shift, not the reduce
             */
            ArrayList<ReduceData> reduces = LALRUtils.getReductionsOf(state);

            // detect shift-reduce conflict
            boolean conflict = false;

            if (shifts.size() > 0)
            {
                if (reduces.size() > 0)
                {
                    // a shift-reduce conflict only occurs when the lookahead of
                    // the Reduce is the SymbolAfterDot of any of the items in
                    // the current state
                    for (ReduceData rd : reduces)
                    {
                        for (Terminal terminal : rd.lookahead)
                        {
                            for (LALRItem itm : state.getItems())
                            {
                                if (itm.getSymbolAfterDot() instanceof Terminal)
                                {
                                    Terminal t = (Terminal)itm.getSymbolAfterDot();

                                    if (t.equals(terminal))
                                    {
                                        conflict = true;
                                    }
                                }

                                if (conflict)
                                {
                                    break;
                                }
                            }

                            if (conflict)
                            {
                                break;
                            }
                        }

                        if (conflict)
                        {
                            break;
                        }
                    }

                    if (conflict)
                    {
                        numConflictShiftReduce++;
                        state.setShiftReduceConflict();
                        System.out.println("WARN: Shift-reduce conflict in \n" + state.toString() + "Solved by prefering shift");
                    }
                }
            }

            if ((reduces.size() > 0) && !conflict)
            { // if we have no shifts, the consider reducing

                Set<Terminal> terminalsSoFar = new HashSet<Terminal>();

                for (ReduceData rd : reduces)
                {
                    if (containsAny(terminalsSoFar, rd.lookahead))
                    {
                        numConflictReduceReduce++; // a conflict
                        state.setReduceReduceConflict();
                        System.out.println("WARN: Reduce-reduce conflict in \n" + state.toString() + "Solved by prefering the first encountered reduce");

                        // solution, don't handle the new one
                        continue;
                    }

                    if (rd.lookahead.isEmpty())
                    {
                        actionTable[state.getId()][defaultAction] = new Reduce(rd.productionId);
                    }
                    else
                    {
                        for (Terminal t : rd.lookahead)
                        {
                            actionTable[state.getId()][t.getId()] = new Reduce(rd.productionId);
                        }
                    }

                    terminalsSoFar.addAll(rd.lookahead); // accumulate to detect further reductions
                }
            }

            ArrayList<GotoData> gotos = LALRUtils.getGotosOf(state); // returns pair list: NonTerminalID, and stateID

            for (GotoData gd : gotos)
            {
                gotoTable[state.getId()][gd.nonTerminalId] = gd.stateID + 1; // zero is reserved for error
            }
        }

        if ((numConflictReduceReduce > 0) || (numConflictShiftReduce > 0))
        {
            System.out.println("WARN: Reduce Reduce Conflicts : " + numConflictReduceReduce);
            System.out.println("WARN: Shift Reduce Conflicts : " + numConflictShiftReduce);
        }

        return new LALRParsingTable(actionTable, gotoTable, terminals, nonTerminals, lalrStates, startProd);
    }

    private static boolean containsAny(Set<Terminal> terminalsSoFar, Set<Terminal> terminals)
    {
        for (Terminal term : terminals)
        {
            if (terminalsSoFar.contains(term))
            {
                return true;
            }
        }

        return false;
    }
}
